// 最小K个数
// 解题方法：①排序取前k个数  ②优先级队列  ③快排
//①
class Solution {
    public int[] smallestK(int[] arr, int k) {
        //排序，取前k个
        int[] ret = new int[k];
        Arrays.sort(arr);
        for(int i = 0; i<k && k<arr.length; i++){
            ret[i] = arr[i];
        }
        
        return ret;
    }
}


//②
import java.util.PriorityQueue;
class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(k==0) return ret;
        //求最小k个数，建k大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2){
                return o2-o1;
            }
        });
        for(int i = 0; i<arr.length; i++){
            if(maxHeap.size()<k){
                maxHeap.offer(arr[i]);
            }else if(arr[i] < maxHeap.peek()){
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
              
        }
        
        for(int i=0;i<k;i++){
            ret[i] = maxHeap.poll();
        }
        return ret;
    }
}


//③
class Solution {
    public int[] smallestK(int[] arr, int k) {
        //快速排序方法 （Hoare法找partition）
        quickSort(arr, 0, arr.length-1, k);
        int[] ret = new int[k];
        for(int i = 0;i<k;i++){
            ret[i] = arr[i];
        }
        return ret;
        
    }

    //快排方法
    public void quickSort(int[] arr, int left, int right, int k){
        if(left>=right){
            return;
        }
        int pivotIndex = partition(arr, left, right);
        int num = pivotIndex-left+1;  //第几个数（从0数）
        if(k==num){
            return;
        } else if(k<num){
            quickSort(arr, left, pivotIndex-1, k);
        }else{
            quickSort(arr, pivotIndex+1, right, k-num);
        }

    }

    //返回基准下标pivotIndex    Hoare法
    public int partition(int[] nums, int left, int right){
        int pivot = nums[left];
        int i = left;
        int j = right;
        while(i<j){
            //先从最右边
            while(i<j && nums[j] >= pivot){
                j--;
            }
            while(i<j && nums[i] <= pivot){
                i++;
            }
            swap(nums, i, j);
        }
        swap(nums, i, left);
        return i;
    }

    //交换数组中两个元素的位置
    public void swap(int[] arr, int i, int j){
        int tmp = 0;
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}